Video or other media signals may be used by a variety of devices, including televisions, broadcast systems, mobile devices, and both laptop and desktop computers. Typically, devices may display or transmit video in response to receipt of video or other media signals, often after decoding the signal from an encoded form. Video signals provided between devices are often encoded using one or more of a variety of encoding and/or compression techniques, and video signals are typically encoded in a manner to be decoded in accordance with a particular standard, such as MPEG-2, MPEG-4, and H.264/MPEG-4 Part 10. By encoding video or other media signals, then decoding the received signals, the amount of data needed to be transmitted between devices may be significantly reduced.
Video encoding is typically performed by encoding 16-by-16 pixel blocks called macroblocks, or other units, of video data. Prediction coding may be used to generate predictive blocks and residual blocks, where the residual blocks represent a difference between a predictive block and the block being coded. Prediction coding may include spatial and/or temporal predictions to remove redundant data in video signals, thereby further increasing the reduction of data needed to be sent or stored. Intracoding for example, is directed to spatial prediction and reducing the amount of spatial redundancy between blocks in a frame or slice. Intercoding, on the other hand, is directed toward temporal prediction and reducing the amount of temporal redundancy between blocks in successive frames or slices. Intercoding may make use of motion prediction to track movement between corresponding blocks of successive frames or slices.
Typically, syntax elements, such as coefficients and motion vectors, may be encoded using one of a variety of encoding techniques (e.g., entropy encoding) and subsequently transmitted between the encoding device and the decoding device. In addition, several approaches may further attempt to optimize syntax elements (e.g. motion vectors, modes, transform coefficients, etc.). Many video encoding methodologies make use of some form of trade off between an achievable data rate and the amount of distortion present in a decoded signal. Trellis optimization techniques may be used to identify an optimal set of syntax elements (e.g. coefficients) that have a minimum rate-distortion cost. Traditional optimization techniques, which also may be referred to as dynamic programming, may encode syntax elements while considering multiple possible coding candidates (e.g. states) for the syntax elements. Optimal states may be selected that lead to a minimum overall cost.